package algorithm_diagram;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//迪克斯特拉算法，用于解决加权图的最小权重问题。不适用于有负权边的加权图（负权边会让已经处理过的节点再更新）。属于贪心（贪婪）算法一种。
public class DijkstrasAlgorithm {

    private static Map<String,Map<String,Double>> graph=new HashMap<>();
    private static List<String> list =new ArrayList<>();

    public static void main(String[] args) {
        dijkstrasAlgorithm01();
    }

    //找出最便宜的节点；对于该节点的邻居，检查是否有前往它们更短的路径，如果有就更新其开销；重复该过程至每一个节点；计算最终路径
    private static void dijkstrasAlgorithm01(){
        graph.put("start",new HashMap<>());
        graph.get("start").put("a",6.0);
        graph.get("start").put("b",2.0);

        graph.put("a",new HashMap<>());
        graph.get("a").put("fin",1.0);

        graph.put("b",new HashMap<>());
        graph.get("b").put("a",3.0);
        graph.get("b").put("fin",5.0);

        graph.put("fin",new HashMap<>());

        Map<String, Double> costs = new HashMap<>();//保存到节点最小权重
        costs.put("a",6.0);
        costs.put("b",2.0);
        costs.put("fin",Double.POSITIVE_INFINITY);//无穷大

        HashMap<String, String> parents = new HashMap<>();//保存到父节点权重最小的子节点
        parents.put("a","start");
        parents.put("b","start");
        parents.put("fin",null );

        String node = findLowestCostNode(costs);//先处理权重最小的节点
        while(node!=null){
            Map<String, Double> neighbors = graph.get(node);//拿到权重最小节点邻居
            for(String n:neighbors.keySet()){
                double newCost = costs.get(node) + neighbors.get(n);//更新经过该节点到邻居节点的新开销
                if(newCost < costs.get(n)){//判断该邻居节点新的开销是否比现开销更小
                    costs.put(n,newCost);//将新开销保存到开销表
                    parents.put(n,node);//更新父表中到该邻居的节点的开销更小的子节点
                }
            }
            list.add(node);
            node=findLowestCostNode(costs);
        }
        System.out.println("从start到fin开销最小的是:"+costs+parents);
    }

    private static String findLowestCostNode(Map<String, Double> costs) {
        Double lowestCost = Double.POSITIVE_INFINITY;
        String lowestCostNode = null;

        for(Map.Entry<String,Double> node:costs.entrySet()){
            Double cost = node.getValue();
            if(cost<lowestCost && !list.contains(node.getKey())){
                lowestCost = cost;
                lowestCostNode = node.getKey();
            }
        }
        return lowestCostNode;
    }
}
